﻿#define _CRT_SECURE_NO_WARNINGS  1
#pragma warning(disable:6031)
#include<stdlib.h>
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>

//18.简单多状态 dp 问题_买卖股票的最佳时机IV_C++

    //状态表示（经验+题目要求）dp[i] 表示第i填结束之后所能得到的最大值
    //f[i][j]表示第i填结束之后完成了j次交易，此时处于买入状态下的最大利润
    //g[i][j]表示第i填结束之后完成了j次交易，此时处于买处状态下的最大利润

    //状态转移方程 ： f[i][j]=max(f[i-1][j],g[i-1][j]-p[i])
    //               g[i][j]=max(g[i-1][j],f[i-1][j-1]+p[i])
    //初始化：f[i][j]=-p[i],g[i][j]=0
    //填表顺序：左到右，上到下；
    //返回值：（最后一行的最大利润（n-1行里面的最大值））

//class Solution
//{
//public:
//    int maxProfit(int k, vector<int>& prices) {
//        int n = prices.size();
//        k = min(k, n / 2);
//        const int INF = 0x3f3f3f3f;
//        vector<vector<int>> f(n, vector<int>(k + 1, -INF));
//        auto g = f;
//        f[0][0] = -prices[0], g[0][0] = 0;
//        for (int i = 1; i < n; i++) {
//            for (int j = 0; j <= k; j++) {
//                f[i][j] = max(f[i - 1][j], g[i - 1][j]);
//                g[i][j] = g[i - 1][j];
//                if (j >= 1) {
//                    g[i][j] = max(g[i][j], f[i - 1][j - 1]);
//                }
//            }
//        }
//        int ret = 0;
//        for (int j = 0; j <= k; j++) {
//            ret = max(ret, g[n - 1][j]);
//        }
//        return ret;
//    }
//};

////二份求解
//
//class Solution {
//public:
//    int maxProfit(int k, vector<int>& prices) {
//        if (prices.empty()) {
//            return 0;
//        }
//
//        int n = prices.size();
//        // 二分查找的上下界
//        int left = 1, right = *max_element(prices.begin(), prices.end());
//        // 存储答案，如果值为 -1 表示二分查找失败
//        int ans = -1;
//        while (left <= right) {
//            // 二分得到当前的斜率（手续费）
//            int c = (left + right) / 2;
//
//            // 使用与 714 题相同的动态规划方法求解出最大收益以及对应的交易次数
//            int buyCount = 0, sellCount = 0;
//            int buy = -prices[0], sell = 0;
//
//            for (int i = 1; i < n; ++i) {
//                if (sell - prices[i] >= buy) {
//                    buy = sell - prices[i];
//                    buyCount = sellCount;
//                }
//                if (buy + prices[i] - c >= sell) {
//                    sell = buy + prices[i] - c;
//                    sellCount = buyCount + 1;
//                }
//            }
//
//            // 如果交易次数大于等于 k，那么可以更新答案
//            // 这里即使交易次数严格大于 k，更新答案也没有关系，因为总能二分到等于 k 的
//            if (sellCount >= k) {
//                // 别忘了加上 kc
//                ans = sell + k * c;
//                left = c + 1;
//            }
//            else {
//                right = c - 1;
//            }
//        }
//
//        // 如果二分查找失败，说明交易次数的限制不是瓶颈
//        // 可以看作交易次数无限，直接使用贪心方法得到答案
//        if (ans == -1) {
//            ans = 0;
//            for (int i = 1; i < n; ++i) {
//                ans += max(prices[i] - prices[i - 1], 0);
//            }
//        }
//
//        return ans;
//    }
//};
//
////作者：zerotrac 🌸
////链接：https ://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/solutions/536396/yi-chong-ji-yu-wqs-er-fen-de-you-xiu-zuo-x36r/
////来源：力扣（LeetCode）
////著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。


 